Skip to main content

Full text of "A Temporal Lagic Programming System"

See other formats


A TEMPORAL LOGIC 
PROGRAMMING SYSTEM 


by 

K. C. MUKHERJEE 


IK* 

C2E. 



M 

mK 

Tf=M 


DEPARTMENT OF COMPUTER SCIENCE a ENGINEERING 

INDIAN INSTITUTE OF TECHNOLOGY, KANPUR 

FEBRUARY. 1988 


A TEMPORAL LOGIC 
PROGRAMMING SYSTEM 


A Thesis Submitted 

In Partial Fulfilment of the Requirements 
for the Degree of 

MASTER OF TECHNOLOGY 


by 

tC C. MUKHERJEE 


to the 

DEPAffTMENT OF COMPUTER SCIENCE » ENGINEERING 

INIHAN mSTITUTE CNP TECHlfOLOGY, KANPUR 

mmuAm, t&m 



■■ jr-'w’ t !' s, T' ■ ._ 

1 1 APR 1589 

CENTR'^L L'^^JARY 

I I T.. KA .!’J■^ 

dec. No. AJA4JlJiL 

C&I'GQS^ 

M8%t 


CSE - l')SS- m - M(y)<-TErvi 



This is to certif7 that the thesis entitled A 
TEMPORAL LOGIC PROGRAMMING SYSTEM is a report of the work 
carried out under our supervision by Krishna Charan 
Mukherjee , and that it has not been submitted elsewhere 
for a degree. 


Dr , H , Kamick 

Asst. Professor 

Department of 
Computet Science 
and Engineering 

I . I . T . Kanpur 

Place : Kanpur , India 



Asst. Professor 

Departiront of 
Ccmtputer Solenoe 
and Engineering 

I.I.T. Kanpur 


Date : February , 1988. 



ACKHOfiLE] 




rs 


It gives me great pleasure to put on record oy feeling 
of gratitude to Dr. R. Sangal and Dr. H. Kamicki my thesis 
supervisors. They suggested the problem and created an 
atmosphere of freedom in which it was a pleasure to work. In 
spite of their busy schedules, they could spare enough time 
to clarify my doubts and ensure smooth progress. 

Special words of gratitude are due to my classmates 
(M.Tech, CS 1986-87) and residents of Hall 4 without whom 
I.I.T-K would have been 18 months of boredom. 



ABSTRACT 


The aim of the thesis is to explore planzxizig and 
understanding. Planning involves selecting a sequence of 
actions to reach a desired state. It includes assessing a 
situation, deciding what goals to pursue, creating plana to 
secure these goals and executing plans. Understanding 
concerns the vay in which a situation is comprehended. In 
this work, we have emphasised on temporal understanding of a 
situation. We have dealt with the issue of reasoning about 
time. 

The logic programming formalism has been chosen for 
the purpose of developing a plan generator and a temporal 
system analyser. In this formalism, the user programs (in 
the form of rules of a logic program) are easier to read. 
They are not cluttered up with details of how things are to 
be done ” they will be more like specifications of what a 
solution will look like. 

The design of a temporal logic .programming syst^ 
helps in overcoming the problem of specification of frame 
axioms which are otherwise needed for handling the notions 
of time, state and history by means of a logic program. In 
addition, the designed system offers a powerful query 
mechanism for reasoning about teianoral relationahiofl. 



CONTENTS 


Chapter Page 

1 INTHOPOCTION 1 

1.1 Plannlzxg and Dnderstandlns 1 

1.2 Overview of the thesis 2 

2 HANDLING STATE, TIME AND BISTOBY 4 

IN LOGIC PROGRAMMING 

2.1 Introduction 4 

2.2 States and Events 4 

2.3 An Example Dcxnain - The Blocks World 5 

2.4 State as an argument of Predicates 8 

2.5 The Frame Problem 14 

2 . 6 Conclusion 17 

3 DESIGN OF A TEMPC»tAL LOGIC 19 

PROGRAMMING FOliliALISM 

3 . 1 Introduction 19 

3.2 The Model of Planning 19 

3.2.1 Inference as Planning 19 

3.2.2 Classificati<»a of Predicates 39 

3.2.3 Notion of Functional Dependency 24 

3.3 Scaaantics of Tosporal Logic ' 29 

Programming rules 

3.4 Need for maintaining History 33 

3.5 Inference in Temporal Logic Progranaiing 35 



Chapter 


Pase 


4 IMPLISIENTATIOH OF A TEHPOBAL LOGIC 39 

PROGRAMMING SYSTEM 

4 . 1 Introduction 39 

4.2 Notion of Temporal Stadcs 39 

4.3 Types of Temporal Stacks 40 

4.4 Creation of Tonporal Stacks 41 

4.5 Update of Temporal Stacks 43 

4.5.1 Nhen to update Tosporal Stacks ? 44 

4.5.2 How to update Temporal Stacks ? 46 

4.6 Resetting Time 53 

5 ANALYSIS AND EVALUATION OF THE SYSTEM 55 

5.1 Special features of the syst^ 55 

5.2 Declarations required in Toaporal 56 

Logic Programming 

5.3 Representing rules in Temporal 57 

Logic PrograBBiiz3g 

5.4 Scope for iaproyement 59 

5 . 5 Conclusion 63 

REFERENCES 64 

APPENDIX - 1 66 

APPENDIX - 2 71 

APPENDIX - 3 72 



CHAPTER 1 


IHTRODOCTIOH 

1.1 Plaxmlug and Onderstandli^ 

How do people understand natural language 7 How do 
they behave rationally in a variety of situations 7 How oan 
computers be made to do likewise 7 

The researcher in the field of Artificial Intelligence 
is interested in extending the capabilities of the computer 
system to encompass common~sense reasoning capabilities. He 
feels the need to explore the nature of knowledge : how it 
oan be represented, how it can be stored and accessed and 
how it can be used in various tasks thouidit to constitute 
cognition. 

The aim of the thesis is to explore such possibilities 
about two areas of cognition - planning and understanding. 
In R. Wilensky’s [14] words "Planning ccmoerns the process 
by which people select a course of action - deciding what 
they want, formulating and revising plans, dealing with 
problems and adversity, making choices and eventually 
performing some action . . . planning includes assessing a 
situation, deciding what goals to pursue, creating plans to 
secure these goals and executiong plans. Understanding 
concerns the way iii, which a person comprehends a situation - 



2 


inferring implicit components, establishing coherence of an 
episode, structuring events into meaningful units and 
finding explanations for various actions." Thus 
understanding involves reasoning about plans and action of 
the people in a situation. In this work, we have emphasised 
on temporal understanding of a situation. We have dealt with 
the issue of reasoning about time. 

The popular logic programming formalism has been 
chosen for the purpose of developing a plan generator and a 
temporal system analyser. This allows reasoning to be done 
in a neat way. The user programs (in the form of rules of a 
logic program) are easier to read. They are not cluttered up 
with details of how things are to be done - they will be 
more like specifications of what a solution will look like. 
The design of a logic programming shell for the purpose of 
plan generation and temporal analysis helped in 
circumventing the problem of specification of frame axioms 
which are otherwise needed for handling the notions of time, 
state and history. 

1.2 Overview of tlM» thesis 

The rest of the thesis describes the design of a 
temporal logic programming formalism and its ‘irapleme^itatlon.' 
In chapter 2, the deficiencies of the existing system fOf 
planning in a logic programming environment .are highlighted, 
This has motivated the need for developing a new f^xiaaii.^m 
which will: assist the user in planning and reasoning about 



3 


time in a more natural way. In chapter 3, the development of 
a temporal logic prograimning formalism is outlined. In 
chapter 4, we describe a logic programming system built by 
using the new formalism. Chapter 5 is an analysis of the 


designed system. 

In 

this chapter, we highlight 

the 

efficiencies 

of 

the 

system and 

also suggest areas 

of 

improvement . 

The 

appendices at the 

end provide the set 

of 


rules for the example domain - Blocks World. We also present 
an interactive session with the temporal logio programming 
system. 



CHAPTER 2 


HANDLING TIME, STATE AND HISTORY IN LOGIC FROGRAmiNG 

2 . 1 Introduction 

The work described here arose in • trying to use the 
logic programming formalism for question answering in the 
context of story understanding. The idea is that since 
answering questions is based on causal connections between 
events and states, it should be possible to use the logic 
programming formalism fairly naturally. However, this raises 
the issues of how time, state and history can be handled in 
logic programming. The state can be incorporated as an 
additional argument of predicates. This will involve 
rewriting of the existing rules of the logic program to take 
care of the state explicitly. The other alternative is to 
modify the logic programming shell so that it handles state, 
time and history implicitly as it executes a logic program. 
The user is expected to broadly guide the system. The 
problem of handling state explicitly is obviated in the 
latter approach. 

2 . 2 States and Events 

A state is something tdnat is true for a while;. false 



5 


for a while, and so on, like the state of Ram being at his 
house or elsewhere. An event is something that can happen 
like Ram going to his house. 

Events are transitions between states. A state token 
is true over an interval of time whereas an event happens 
; it is either instantaneous or has a beginning, middle and 
end. Practical programs have to worry about these concepts 
for two reasons. First, things change. A realistic database 
must keep track of what is true at various times and not 
just the present. Second, the machine may have at its 
disposal ways of intervening in the world in order to 
achieve its goals. 



2.3 An Example Domain - The Blocks World 

The Blocks World [11,13] is chosen to illustrate the 
concept of states, actions and how states change due to 
actions. The world consists of a plane surface or table with 
blocks on it. The blocks are labelled and may be stacked in 
various ways. The position and configuration of the blocks 
are known. There is a robot arm that can move the blocks. 

Knowledge about the Blocks World is specified in terms 
of general rules, and inferring the solution to a problem is 
done by instantiating the rules to a particular situation. 




6 


Knowledge is represented as Horn clauses in a FB0l/>Q C33 
like system. Knowledge will be represented as ruies and 
■facts. The rules are applicable to . a variety of 

situations.- They usually contain variables. facts are 
specific and do not contain variables. The following is a 
fact (on A B) which states that block A is on top of 
block B . It consists of a predicate on applied to A 
and B . The predicate on is true of two blocks if and 
only if the first one is on top of the second. A predidate 
applied to arguments is called predication. The rules are 
implications consisting of a left hand side and a right hand 
side. The left hand side has a predication and the ri^t 
hand side has one or more predications. Its meaning is that 
the left hand side can be inferred provided the predications 
on the right hand side hold. In a rule , the prefix ? 
will be reserved for logical variables. These variables may 
vary over any object in the database. The following is an 
example of a rule : - 


roller ?x ?yJ <- (block (block (on * 

It asserts that an arbitrary block 9x is . over anotli^ 
arbitrary block ?y if ?x is on ?y . ?x bui 4 ?y aire 
variables that may be instantiated by blocks. 

Infea^ence is done in, -the ‘Standard logic pirograaning 
fashion. To know, whether A is over c , we pose a < 3 idbry 
like ? (over The inference proceeds in the 



7 


following manner . First, we check whether a query or a goal 
already matches with a fact already present. If yes, the 
query is true. In case the query fails to match with any of 
the given facts, we try matching it with the loft hand side 
(consequent) of the rules. If a rule matches, the predicates 
on its right hand side (antecedents) after proper 
instantiation b.ecome the subgoals. In case of failure to 
match a subgoal we try another rule. The process repeats 
until we are successful or no more rules for a particular 
predicate remain. 

The Robot Ara is an important component of the i 
Blocks World problem.lt can perform three operations. It can 
open open or close its gripper to grasp or ungrasp a block. 
It can also be made to move to a desired position. The three 
special predicates that relate to the actions of the robot 
arm are : - 

(grip) — close the gripper 
(ungrip) — open the gripper 

(wove-robot-erm ?x ?y ?z) — move the robot arm to 7x, ?y 
& ?z coordinates of a three-dimensional space 

Determining the truth value of these predicates causes the 
robot arm to be actuated. For modelling the state of the 
Blocks World, , the predicates are .as follows!” 

(posn ?block ?y ?z) true in the state where tha 
position, of the ?biock is 7x , .?y and ?z. 



8 


(on ?biockl ?biock2} — true in the state where ?blociEl 
is on top of ?block2. 

(clear 7block) — true in the state where ?block is 
clear ( i . e . no other block is on it ) . 

(grasp ? block} — true in the state where ?block is 
clear and gripped by the robot arm. 

(posn-hand ?x ?y ?z} — true in the state where the 

robot arm is positioned at coordinates ?x , ?y and ?2. 

(handeupty} -- true, in the state where the robot arm is 
not gripping any block and is empty. 

The truth values of these predicates describe a particular 
state. When the state of the Blocks World changes i.e. we 
move from one state to another there is a change in the 
truth value of one or more of those state description 
predicates. 

2.4 State as an argument of predicates 

With the idea of keeping track of the changing 
database of facts with time as well as to answer time- . 
related questions, the first solution attempted was by 
incorporating a state or situation variable in each of 
the predicates whose truth values can change from state to 
state. The idea was in accordance with Green's formulation 
[5,10]. By this, the robot problems formulated in such a 
way that a resolution theorem proving system can solve them. 
This formulation involved one set of assertions that 



9 


described the initial state and another set that described 
the effects of various robot actions on the states. The goal 
condition was then described by a formula with an 
existentially qucintified state variable. That is, the 
system would attempt to prove that there existed a state in 
which a certain condition was true. A constructive proof 
method could then be used to produce the set of actions 
required to create the desired state. In other words, the 
entire pi art or the sequence of primitive actions needed 
for moving from the initial state to the final state would 
be unified with the state variable of the goal formula. The 
deduction system used was the logic programming shell - 
•'VIDHI“ [12]. An example to illustrate the above notion is 
as follows 

Suppose the primitive actions which constitute a plan a;re 

( 1 ) (grasp ?b2ock} 

(2) (ungrasp ?block} and 

(3) (move-hand— to 7x 7y 7z} 

where the symbols have their usual significance. Let the 
initial state be designated by S#- An example 
configuration of blocks in the initial state is given by the 
following facts in VIDHI 

(defasrt 1 ( init ial-state S0) ) 

(defasrt 2 (block A)) 

(defasrt 3 (block B) ) 

(defasrt 4 (is—pgsn A i i 1 



{de-fatsrt 5 (xs-posn B 2 2 2 80} J 


Cdefasri 6 (ht A 2}} 

(de-fasrt 7 (ht B 2}} 

(defasri 3 (is~claar A 80} > 

(de-fasrt 9 ( is-cJear B 80}} 

(de-fasrt 10 (is-posn-hatnd 3 3 3 80} } 

From the above the facts that are true about the blocks { A 
and B ) as well as about the robot-ana are clear . In 
this method of using state variables explicitly as arguments 
of predicates, the special functional expression (*<io 
<action> <state>} is used to denote the function that maps 
<state> into another state resulting from the <action> in 
<state>. Thus by first moving the robot arm to the position 
(i 1 1) , we move from the initial state 80 to the state 
given by (^do (move^hand-^to 111} 80} » Now , the rule 

for putting a block on top of another is formulated as 

(detasrt 11 (on ?blockl ?block2 

(*do (ungrasp ?blockl} 

<»do (wove-hand-to ?x2 7y2 ?z~-comp} 

(*do (grasp ?bIockl} 

(*do (move-hand-to ?xl 7yl 7x1} 7s}}}}} <— 
(is-^clear 7blockl 7s} 

< is-clear 7block2 7s) 

(is'^p&sn 7b Jock $ 7x1 fyl 7zl 7s} 



11 


(is—posn—hand ?xh ?yh 7zh ?s} 

(not (= 7x1 7xh)> 

(not (= 7yl 7yh}} 

(not (= 7zl 7zh}} 

(is~posn 7block2 7x2 7y2 7z2 7s) 

(ht 7blockl 7hl) 

(ht 7block2 7h2) 

(- 7z-comp ?z2 (» 0.5 7h2) (M 0.5 ?hl))) 


So , when we set a goal as (goal (on A B 7st)) , the logic 

programming formalism is used to derive the answer for the 
state 7sf in which A is on top of B - By using the 
rule given for on and the facts asserted about -Mie initial 
state S0 in the database, the value for is obtained 

as 

7sf * (iido (ungrasp A) 

(Kdo (mot^e-hand-to 2 2 4) 

<*do (grasp A) 

(*do (move—hand-to 111) S0)))) 

In this way, the final state 7sf is a result Of executing 
a series of primitive actions on the initial state Sg, 
where each primitive action causes a transition from one 
state to another. By this method, the plan needed for 
putting the block A on top of block 8 is essentially 
captured in the unifier for the final state variable 7sf . 



12 “ 


We "then explored the possibilities when the state 
variable is included as an explicit argument of the 
predicates. Temporal understanding of plans and qualitative 
reasoning about time were provided as additional features by 
means of rules of a logic program. The primitive actions, 
which have been listed before were considered to be ti*e- 
setters, that is, they caused a change in state and also 
incremented the clock. So, the initial set of facts asserted 
about the Blocks World are a true description of the initial 
state at the zeroth instant of time. Subsequently, as a plan 
is generated to achieve a desired state, in which a certain 
relation becomes true, the final state is expressed as an 
effect of the plan on the initial state. In order to proceed 
from the initial state to the final state by sequentially 
executing the primitive actions of the plan, we move through 
several instants of time. Analysing the example mentioned, 



13 


(posn A 1 1 1) 
(posn B 2 2 2) 
(clear A) 

(clear B) 

(posn-Kand 333) 

- 

(posn A 1 1 1) 
(posn B 2 2 2) 
(clear A) 

(clear B) 

fposn-hand 111) 

(move-hand-to 

111) 

State = S0 


State = SI 

time = 0 


time = 1 

*{posn A 2 2 4) 


(posn A 1 1 1) 

(held A) 


(held A) 

(clear A) 1 

< 

(clear A) 

(posn B 2 2 2) 

1 

(move-hand-to 

(posn B 2 2 2) * 


2 2 4) 


(clear B) 


(clear B) 

Ifposn-hand 2 2 4) 


(posn -hand 111) 

State = S3 


State = S2 

time = 3 


time = 2 


■ , Ml > 

(posn A 2 2 4) 
(clear A) 
(posn-hand 224) 

{ ungrasp A) 



(posn B 2 2 2) 


l(cl-e«rr51 


State = Sf 
time = 4 


As a transition takes place from one state to another, the 
following will happen '• 

( 1 ) Time is incremented since a primitive action has taken 

place . . 

( 2 ) Some of the existing state description predicates may 
change (illustrated hy a * in the diagram) 







14 - 


(3) New state description, predicates aay become true 
(illustrated by j j ). 


(4) Old state description predicates may cease to be valid 
in the new state (illustrated by ^ CTj 
diagram) . 


This changing state description causes different 
relations to become true at different instants of time. For 
example, the relations <cleatr A) and ^cJear B) are 
coincident in time i.e. they are jointly true at time 
instants = 0,1,2 and 3. Again the relation fposn-hand 3 3 

3} precedes the relation (held Al in time as the former 
is true at the time instant = 0 while the latter becomes 
true at time instant = 2. We could also say that the 
relation (held A) follows the relation (posn'^hatid 3 3 31 
in time. 

When the state is used as an explicit argument of 
predicates, temporal analysis of the Blocks World for a 
given plan can be done by the use of additional rules i.e. 
rules in addition to those required for plan .generation. 
Time comparisons between relations can be made by examining 
the final state (expressed in terms of the plan and initial 
state) and the inteirmediate states. 

2.5 The Frame Problem 

To us© a familiar analogy, the changes between on© 
state description and another can be compared to changes 



15 


’ ^ 

between frames in an animated film. The problem of 
specifying which formulas in a state description should 
change and which should not is called the frame problem in 
Artificial Intelligence. When the state variable is used as 
an additional argument of predicates and the logic 
programming formalism is being used to solve the problem of 
plan generation and temporal analysis we must completely 
specify the effects of an action on an existing state. We 
must also state that certain relations are unaffected by the 
action. Here, the "effects" and "non-effects'* alike need to 
be stated explicitly. Using Green's formulation, we must 
have assertion for each relation not affected by an action 
or a sequence of actions. Using a state variable as ^ 
explicit argument of predicates, we observe that a number of 

assertions have to be made to emphasise the "non-effects" of. 

» 

various actions. For example, the following assertion is 
needed to state the fact that when the robot arm is moved to 
the position of a block, the block grasped, the hand moved 
to a different position and then the block released, the 
position of another block remains unchanged. 

(defasrt ipb2 (is-posn ?b2ock ?x ?y 7z 
(*4o (ungrasp ?blockll 
(*do (move-hand-to 7x2 7y2 7z2} 

(*do (grasp 7blockl> 

(»do (mov e-hart d-to 7x1 7yl 7zi) 7s})})} <- 
(diffrnt-blocks 7blockl 7block} 

(is-posn ?block ?x 7y 7x 7s}} 



16 


Similarly, by the second assertion, a block remains on 
top of another when a third different block undergoes the 
above sequence of actions. 

CdetasTt ioTi2 (is— on ?blockl ?block 
(*do (uTi grasp ?block2> 

(*do (move -band— to 7x1 7yl ?zl} 

(*do (grasp ?block2) 

(*do (move-ban d-to ?x 7y 7x1 7s}}}}} <- 
(diffrnt— blocks ?block 7blockl} 

(diffrnt— blocks 7block 7block2} 

(diffrnt— blocks 7blockl ?bIock2} 

(is-on 7b2ockl 7block2} ) 

By the third assertion, a block continues to be held in 
the resulting state when the robot arm is moved in a 
particular state. 

(defasrt ibb3 (is-beld 7block (*do (move-hand-to 7x 7y 
7z) 7s}) <- 

(is-beld ?block 7s)} 

The predicate (diffrni-blocks 7x ?y} is true when 7x and 
?y are unified to different blocks. 

The assertion describing what stays the same during an 
action are palled the frame assertions or frame axioms - 
In large systems, there may be many predicates used to 



17 


describe a situation. By using Green's formulation, a 
separate frame assertion is needed for each predicate. By 
using Kowalski’s formulation [6,7], the statement of the 
frame assertion may be simplified but not removed totally. 

What would ordinarily be predicates in Green’s 
formulation are made terms in Kowalski’s formulation. This 
simplifies the frame assertions . Here, only one frame 
axiom is needed for each action. For example, instead of 
using the literal (on A D s&) to denote the fact that A 
is on D in S0, we use the literal (bolds (on A DJ . 

The term (on A D) denotes the “concept” of ^ being on 
0- Suppose the robot has an action that can “transfer” i 

block 7x from position ?y to position ?z where 
and ?z . might be either names of other blocks that block 
might be resting on or names of positions on the table. 
Let us assume that both block 7x and position ?r must be 
clear to execute the action. We model this by (trans 9x ?y 
?z) . Now we express part of the effects of the actions by 
using a separate holds literal for each relation made true 
by the action. For example, 

(holds (clear ?x> (*do (trans 7x ?y 7z) ?s}) 

(holds (clear 9y} (*do (trans ?x ?y ?z) 7s>} 

(holds (on 7x 7zl (edo (trans 7x 7y ?z) 7s-}) . 

The major advantage of Kowalski’s formulation is that we 

need only one frame as^sertion for each action. In our 



18 


example, the single frame assertion is : 

{ <bolds 7v 7s} /\Cfiiff 7v (clear 7x1 } /\(diff 7y (on 7x 
7y}} } -> 

(holds 7v (*do (trans 7x 7y 7x1 7s}} 

This expression quite simply states that all terms different 
than (clear 7x} and (on 7x 7y} still hold in all 
states produced by performing the action (trans 7x 7y 7x1 # 

2.6 Conclusion 

From the proceeding discussion, we see that although 
plan generation and temporal analysis can be done through 


the existing 

logic 

programming 

formalism 

(VIDHI) 

by 

incorporation 

of 

state 

as an 

additional 

argument 

of 

predicates, the 

process is 

cumbersome and not 

attractive 

to 


a user of the system. The responsibility of reasoning about 
states, maintaining the state transitions with actions etc. 
is forced upon the writer of the logic program. He has to 
also make a number of frame assertions to get an accurate 
picture of the changing states with time. Further, an 
equally important disadvantage is the inefficiency of the 
frame axioms. 

In order to relieve the user of such burdensome 
programming, a more sophisticated reasoning system was 
developed on top of the existing logic programming shell - 
Vidhi. This enables the experienced user to generate plans 
and do temporal analysis in a more natural way. 



CHAPTER 3 


DESIGN OF A TEMPORAL LOGIC PROGRAMMING FORMALISM 


3 . 1 Introduction, 

In light of the problems mentioned in the previous 
chapter, we need a . logic programming system which would 
accept user’s program (set of rules) and implicitly reason 
about state, time and history. The user is then relieved of 
the burden of taking care of state explicitly through his 
logic program. 

In this chapter we describe our temporal logic 
programming formalism. 

3.2 The Model of Planning 
3.2.1 Inference as Planning 

The desired sequence of actions needed for achieving a 
goal is called a plan for achieving the goal. The goal may 
be looked upon as a desired state into which the planning 
world is to be transformed. Given the goal, the planner must 
assess (or observe) the existing situation. If it finds that 
the current state of the world is not the desired ( or the 
goal) state, it generates the plan required for 
transforming the existing state to the goal state. Thus 
planning accounts for a ntuaber of cognitive processes. They 



20 - 


include assessing a situation, deciding what goals to 
pursue, creating plans to secure these goals and executing 
plans. In the context of logic progranuaing, the process of 
inference of a goal state from an initial state generates 
the plan as an answer substitution for the state variable 
when it is used explicitly (see chapter 2). When the state 
variable is removed the interpreter maintains a history of 
states from which the plan is generated. 

3.2.2 Classification of Predicates 

When the above structure of planning is to be captured 
by means of rules of a logic program states as well as 
changes in the states are modelled by predicates. Thus the 
classification of predicates becomes necessary. Given sm 
initial state of the world, the goal ■ would desire to 
transform the world to some other state and ash for the plan 
needed for doing so. Referring to the earlier example of the 
Blocks World, the initial statei is sg . In this state, 

blocks A and B are lying on the table. Now, a plan may 
be required to be generated for stacking on B . After 
executing the plan the Blocks World will be transferred to a 
new state where A will be on B , The required plan oaua 
be generated by setting up the goal (on A B) . Here on 

can be looked upon as a desired state predicate . A 

* ♦ 

desired state predication essentially expresses what should 
be true in a certain state. Therefore, it first observes 
whether the predication is true in the existing state or 



21 


not. If it is, then nothing has to be done, else actions are 
to be executed in a certain sequence to transform the world 
to the desired state where the predication becomes true. 
This necessitates further classification of predicates into 
state observation and action predicates respectively. 
Summarising the above information, we get 

(1) State Observation predicates These predicates 
refer to the state implicitly . They do not cause any 
change in state when tested for satisfaction. In the 
rules 

(posn ?block ?x ?y ?z) <- (is-posn Pblock ?x ?y ?z) 
(clear Pblock) <— (is-clear Pblock) 

(on Pblocki Pblock?) <- (is-on Pblockl Pblock?) 

* 

is-clear , is-posn , is-on are examples of state 
observation predicates . 

In general , the user will specify certain 
dependency rules among the various state observation 

i 

predicates used in modelling the planning world . Soiae 
of these predicates are independent i.e. they do not 
have any rules defining 'them in terms of other 
predicates. The others are dependent on other state 
observation predicates i.e, they have rules where 

i 

other ' state observation predicates appear as 
antecedents. In our Blocks World, the different state 
observation predicates are is-place , is-posn , is- 
gripped , is-on , is— clear t is-grasp , is-loaded , is- 



22 


handeapty , is-posn-harid etc. Predicates such as is- 
posn , is-posn-hand and is~gr ipped have no rules 
associated with them and hence are independent state 
observation predicates. The others have rules 
associated with them - for example, 

(is-grasp ?block} <— (is—posn 7b lock 7x 7y ?z) 

( is-posn-hand ?x ?y ?z} 

<is~gr ipped) 


(2) Desired State predicates These predicates may 
cause change in state when tested for truth value. If 
the desired state does not hold, it may cause actions to 
be initiated to achieve the desired state. In the above 
rules, predicates like on , clear , posn are examples 
of such predicates . 

There exists a correspondence between desired 
state predicates and state observation predicates. 
The first rule for any desired state predicate 
involves state observation. It typically has the 
desired state predicate in the consequent and a state 
observation predicate in the antecedent. Only in case 
of failure are the subsequent action rules executed . 

• Inferring a desired state predicate results in 
the change in truth value of some state observation 
predicate (the state observation may have to be 

asserted or retracted i.e. its negation may have to be 



- 23 


asserted) . For specifying such assertions, a s^>ecial 
predicate - asserth may be included as an antecedent 
of the desired state predicate. This predicate, in 
conjunction with a special form of cut facility (see 
later) can cause a number of assertions to be made 
{depending on what pre-conditions are satisfied) about 
various state observation predicates after a desired 
state predicate is inferred. 

(3) Action predicates Corresponding to actions to 
be taken in the plan, we have action predicates. 
Predicates corresponding to primitive actions may be 
designated as time-setters . In the rules 
(grip) <- (ciose-gr ipper) 

(angrip) <— (open-gripper) 

(posn-hand 9x ?y ?z) <- (move-robot-arm ?x ?y 9z) 

close-gripper , open-gripper , move-robot -arm are 
examples of such predicates . 

In the context of planning, a task may be 
decomposed into several subtasks. It is the structure of 
these subtasks which determine the plan necessary for 
executing the task. At the bottom of the hierarchy are 
found primitive tasks whose execution requires no 
planning to be carried out-. The primitive tasks cannot 
be broken down any further. Which actions Count as 
primitive depends on the available hardware and how 



24 


■the Blocks World, the three basic robot arm operations 
considered as primitive are open-gripper , close- 
gripper and move-robot-erm The planner is started 
with a task, which it must reduce to these primitive 
actions. These primitive actions are also designated as 
tine-setters The inferring of the time-setters causes 
an incrementing of the clock and moving ahead with 
respect to time. Through this mechanism a linear 
ordering of the states of the Blocks World with respect 
to time takes place. 

3.2,3 Notion of Functional Dependency 

The temporal predicates define relations between 
jertain entities in the planning domain to certain 
attributes . In the domain of the Blocks World, the entities 
ire the blocks about which attributes such as positional 
loordinates (x , y , a) are asserted at different points of 
:ime. 

In general, the relations defined by the temporal 
?redicateis are functional in nature [9] . For example, 
3onsider the predicate posn with four arguements *• (posn 
>b 7x ?y ?z) . It describes the relation that the block 
^b is at the position whose coordinates are given by ?x , 
>y , ?z • We say that the last three arguments (positional 
coordinates) are functions of the first argument (block), A 
clock uniquely determines the position in which it is 
situated at any given instant. Two different blocks cannot 



25 


be at the same position at any given instant. Formally, a 
functional relation F is said to exist among the arguments 
of a predicate P if a set of arguments at positions I of P 
uniquely determines a set of arguments at positions D of P. 

F : I --> D for predicate P 

sets I and D are known as set of independent (key) and 
dependent (non-key) arguments of P respectively. In the 
temporal predicates of the Blocks World, which relate 
entities or blocks to different attributes, the entities may 
be looked upon as the keys of the relation. 

3,3 Semantics of Temporal Logic Programming Buies 

In the present system, the pi an- generation rules of 
the usSr have no explicit references to state and timei In 
this section, we outline a method by which these rules aiay 
be transformed to a set of rules where the state variables 
and their ordering become explicit in the formulation of the 
rules. Thus the method helps in clearly defihisgig the 
temporal semantics of the user's rules. : 

To illustrate the above, let us consider the example 
of grasping a block in the Blocks World. The user defined . 
rules are as follows 

(grsisp 7block} <— (is-gratsp ?block) 

(grasp ?b2ock) <— (block ?biock> 


(clear ?block) 



26 


(han dBvipty) 

(is-posT> ?block ?x ?y ?z} 

( posn—lrand ?x ?y 
(grip} 

The corresponding rules wi-th explicit use of state 
variables as arguments of predicates are : 

(grasp ?bIock ?S ?S1 <- ( is-gr asp ?block 75) 

{ the desired state (?S) remains the same as the initial 
state (?S) when the state observation is satisfied at the 
initial state (?S) } 

(grasp ?bIock ?Si 7Sf} <- (block ?block> 

(clear 9block ?Si ?S1} 

(handewpty ?Si ?S2) 

(is-posn ?block ?x ?y ?x ?S2i 
(posn-hand ?x 7y 7z 7S2 ?S3; 
(grip 7S3 734} 

(= 7Sf (do-grasp 7block 7S4)) 

Here, every desired state predicate - grasp, clear, 
handewpty , posn-hand, grip have two additional state 
variables as arguments. The desired state, on being 
achieved, transforms the Blocks -World from the first 
state to the second. Thus in our example. 



?Si 


(grasp ?bloc.k} > 7Sf 


The state observation predicates, on the other hand, have 
only a single additional state variable in the list of 
arguments. They check for satisfaction in that particular 
state. In the example, (is-posn ?block ?x ?y ?z ?S2} is 
true when a block ?block has positional coordinates ?x , 
?y f 7z in the state ?S2 . 

The ordering of states, which was implicit in the 
original set of rules now becomes explicit. There is a 
sequence on the literals in the body of the rules. On 
examining the antecedents of the rules for the desired 
state predicates, we find that the planning world moves 
through a number of intermediate states in the process of 
transition, from the initial state to the final state. In 
the example, (grasp ?block> causes the Blocks -World to 
transit from the initial state ?Sx to final state 
In the process it moves through the intermediate states 
9S3 and ?S4 if required. 

By this mechanism, we can also reflect the linear 
ordering of states with respect to time. In general, the 
state that results on activating a time-setter follows the 
state that existed before activating the time-setter in 
time. The concept can be illustrated by considering the 
rules for grip , 



28 


(grip PS PS) <— ( is-gr ipped PS} 

(grip PSi PSf ) <— (close-gripper PSi PS-fl 

(= PS-f (do-close— gr ipper PSi}} 

where (i/o(’close-gr ipper Ps) produces a shahe which 
inunediately follows state ?s in time. The incrementing in 
time is brought about by inferring the t2»e-setter 
close-gripper . 

The plan for achieving the goal state is obtained as 
the unification of the second state variable in the desired 
state predicate of the goal. Looking at an example of the 
Blocks-World, let the initial configuration be : 

(defasrt 1 (block Al ) 

(defasrt 2 (block El) 

(defasrt 3 (is-posn A i 1 1 Sil) 

(defasrt 4 (is-posn B 2 2 2 Si}) 

(defasrt 5 (Ht A 2) ) 

(defasrt 6 (Ht B 2)) 

(defasrt 7 ( is-clear A Si}) 

(defasrt 8 ( is-clear B Si)} 


(defasrt 9 ( is-posn-band 333 Si)) 



29 


Using -the transformed rules where the state variableaj 
are explicit arguments of predicates, the goal Con A B ?Si 
7 St'} produces the unification for ?Sf as 

Cdo-place A (do-open— gr ipper Cdo-posn A 2 2 4- (do-move- 
robot-ar-m 2 2 4 (do-grasp A (do— close— gr ipper (do— 'move— 

robot-arm 111 Si)))})!} , 

This is the plan for putting A on B. It is to be interpreted 
as - move the robot arm to (111), close the gripper 
thereby grasping A. After that, move the robot arm to (2 2 

4) thereby positioning A to (2 2 4) and finally opening the 
gripper placing A at (2 2 4) which is on top of B. 

In order to formulate the generalised scheme for 
transformation of the plan-generation rules without explicit 
state variables to a set of rules with the variables 
explicit, we partition the set of plan-generating rules in 
two classes - 

(1) desired state predication rules : These rules 
typically have desired state predicates as consequents. 
Every desired state predicate, in general, has two rules 
associated with it. The first rule is the observation 
rule, in which it invokes a state observation predicate 
and action rule in which it invokes in general other- 
desired state predicates, time-setters along with non- 
temporal and other state observation predicates. 

(2) state observat ion predication rules : These rules 

typically have state observation 


predicates as 



30 - 


consequents. In the antecedents are other state observation 
predicates. This set of rules expresses relationship^' 
between different state observat ion predicates. 

We define eleaentary desired state predicates as 
those which invoke time-setters or ''primitive actions" in 
their action rules. That is these desired state 
predicates cannot be expressed in terms of any other 
desired state predicates. On the other hand, compound 
desired state predicates invoke other desired state 
predicates in their action rules. In the Blocks World, on 
is a compound desired state predicate, whereas, grip is 
an elementary desired state predicate. 

The scheme for transforming desired state predication 

» 

rules is as follows : 

(1) If the rule is of the observation type then 

(i) introduce two additional state variables as 

arguments of the desired state predicate in the 

consequent of the rule. These variables are identical. 
Let them be 9S and 9S. 

(ii) introduce the same state variable ?S as an 
additional argument of the state observation 
predicate in the antecedent of the rule. 

(2) If the rule is of the action type then 

(i) introduce two additional st^te variables as 

> 

arguments of the desired state predicate in tHfe 



31 


consequent of the rule . Let these be 9Si and 
in that order respectively. 

(ii) For the antecedents of the rule do 

(a) If the antecedent involves non-temporal 
predication leave it as it is. 

(b) If the antecedent is a time-setiBr th^n 
introduce ?Si and ?Sf as its additional 
arguments. 

I 

(c) If the antecedent involves desired state 

r r 

predication then add two additional intermediate 
state variables as arguments in the antecedent. If 
the antecedent is first in the list of antecedents 
of the rule then the first additional variable is 
7Si, If the antecedent is last in the list of 

antecedents of the rule then the second additional 
variable is 

(c) If the antecedent involves state obseryation 
predication then include the second state varialxle 
of the previous desired state predicate in the 
antecedent list as an additional argument of the 
state obsetvation predicate. ' 

(iii) If the desired state predicate ( dsp ) ^in 
the consequent of the rule is elementary (i.e, it 
invokes a time-setter ( ts )) 

then add an antecedent of the form 7Sf(M:s 7Si}} 
else ( dsp is compound ) add an antecedent of the 



32 


form <= ?S-f(Sdsp arg^ 
where 

dsp denotes desired state predicate 
arg^ ... arg^ denote arguments of dsp 
?Sint denotes previous intermediate state i.e. 
second state variable argument of the Iasi desired 
state predicate in the list of antecedents of the 
desired state predication rule. 

The scheme for transforming the state observation 
predication rules is as follows : 

(i) Introduce an additional state variable as argument 
of the state obseryation predicate in the consequent 
of the rule ( ?s ) . 

(ii) For each of the antecedents of the rule do 

(a) If the antecedent is non-temporal then leave it 
as it is 

(b) If the antecedent involves state observation 
predicate then add the same variable ( ?S ) as an 
additional argument of the predicate. 

The above scheme of generating plan helps in writing 
of the ■frame axioms for the independent state observation 
predicates. We can recall the fact that a state variable 
may be unified to a constant (the initiai state argument ) 
or a list formed from successive applications of desired 
state predicates and time-setters on some initial state. 



33 


For every iridependent state observation predica^te ( sopi 
) with argument list ( arg^ ... ^ introduce the 

rules state that (i) the independent state observation 
predication is not affected in a state formed by the 
inferring of a desired state predicate which does not 
invoke it in the observation rule and (ii) the 
independent state observation predication is not affected 

by the inferring of a desired state predicate when the 
keys of the predications do not match. The rules are as 
follows : 

(sopi arg ^ ... ^>^9^ <- 

(not (initial-state 7s) > 

( is-t i»e— setter (car ?s)) 

(sopi arg^ ... (sett (car ?S} (dsp-for-ts (car ?s)))} 

(sopi af'Sj 

(not ( initial— state 73)) 

(not ( sop-tbr-dsp sopi (car 7S) > ) 

(sopi (predecessor ?SJ) 

(sopi arg^ ... arg 7S) <— 

1 n 

(initial-state 7s)> 


(= 7key^ 

(extr-key 

sopi 

^rg^ 

, , arg }} 


(extr—key 

( car 

?S) 

(get-args (car ?S} ?SJ}) 


(not (equal ?key ^ ?key^)) 

(sopi arg^ ... srg^ (predecessor 7S)) 

where 



34 


(initial-state ?s} i returns true if 9s is bound to the 
initial state. 

(is-tine-setter ?x) s returns true if 9x is bound to a 
do-tijae— setter else it returns nil, 

(predecessor ?s} : returns the state proceeding state 9s 
in time. 

(extr-key pred arg^ the Icey-list of 

the predicate pred from the list of arguments •" 

arg 

(sop—for-dsp 9sop 9dsp) s returns true if 9sop is the 
state observation predicate for the desired state 
predicate 9dsp else it returns nil. 

(dsp-for—ts ?x> s returns the eleaentary desi^d state 

,*• 

predicate which invoked the time-setter - 9x. 

3.4 Need for maintaining History 

AI databases are not static. Assertions come and go 

* 

and the inferences they trigger must be kept upto date. A 
realistic database must keep track of what’s true at various 
times, not just the present. As the planning world transits 
from one state to another, due to the occurrence of events, 
the various relations which are true in different states 
constitute the state descriptions at those instants. A 
record of what is true at different points of time 
constitutes the history of the planning world. In order to 



35 - 


do temporal analysis of generated plans, we cannot get away 
with representing just one situation (the "current" one) and 
must find some way to implement a database in which many 
different situations are stored. For example, in our Blocks 
World, the position of a block may change from one state to 
another (hence from time to time). In order to infer the 
position of the block at some earlier instant of time, a 
record of the varying positions of the block with time must 
maintained. Hence, we clearly feel the need of storing 
history , 

In the context of logic programming, the temporal 
predicates need to , refer to history for their 
satisfaction. These predicates constitute the method by 
which temporal question answering is possible. They are also 
referred to in the course of plan generation. In the course 
of plan generation, we may feel the need of placing block A 

at the position in which the block B was at a certain 
instant of time. Hence the plan generating rules may refer 
to the history of the Blocks World in order to infer where 
B was at the required instant of time. Only then can a 
suitable plan for placing A be generated. 

3 . 5 Inference in Temporal Logic Programming 

The execution of a plan causes the planning domain 
to move through several states. In the course of this 
transition, the time is incremented. Different state 
descriptions hold true at different instants of time. The 



36 


temporal logic programming system keeps track of the 
changing states and history of the world by means of 
temporal stacks. The procedure adopted for doing this will 
be explained in the following chapter. In addition, the 
system also has the ability to reason about time and 
comprehend time-related events. The system is able to answer 
questions regarding time in a typical logic programming 
fashion. It is able to answer questions regarding 
occurrence of events at particular time instants, as well 
as, examine the validity of properties over time intervals. 
The temporal logic used for this purpose is as follows : 

There are two predicates holds-xnst and holds- 
int . { hoids-iTist ?p?t ) is satisfied when a property 

is holds (i.e. true) at a time instant ?t , ( 

holds-int 7p ?t ) is satisfied when a property ?p holds 
over a time interval (list of time instants) . 

To know, for example, when block A is on block B the 
user can set up a query : iquery <holds-inst (on A B/ ?t>> 
or (query (holds— int (on A B) ?tf) . If (on A SI 3 
true at time instants 0, 1, 2, ,3, 7, 8, 9 - then the first 
query will return 0, 1, 2 ... one after another. The second 
query, on the other hand, will return (0 3) and (7 9) as 
answers . 

These two predicates can also be used in conjunction witli 
other mutually exclusive primitive relations [1,8] that can 
hold between temporal intervals (or time instants) to make 



37 


meaningful queries . 

There is a basic set of mutually exclusive primitive 
relations that can hold between temporal intervals. Each of 
these is represented by a predicate in the logic. These 
relationships are summarised in the definitions and the 
accompanying figure. 

(During 7tl 7t2} : time interval 7tl is fully 
contained within 7t2 . 

(Starts 7tl ?t2} s time interval 7ti shares the 

same beginning as 7t2 but ends before 7t2 ends. 

(Finishes 7ti ?t2J s time interval 7tl shares the 
same end as ?t2 but begins after 7t2 begins. 

(Before ?tl ?t2) s time interval ?tl is before 

interval ?t2 and they do not overlap in any way. 

(Overlap 7tl ?t2) s time interval 7tl starts before 
interval ?t2 and they overlap. 

^r/feets ?tl 7t2) s time interval 7tl is before 

interval 7t2 but there is no interval between them i.e. 

7ti ends where 7t2 starts. 

(Equal 7ti 7t2i s ?ti and 7t2 are the same 
interval,. 

Relation Pictorial Example 


X before Y 


XXX YYY 



38 


X equal Y XXX 

YYY 

X meets Y XXXYYY 

X overlaps Y XXX 

YYY 

X during Y XXX 

YYYYYYY 

X starts Y XXX 

YYYYY 

X finishes Y XXX 

YYYYYY 


Similar relationships can also be developed in 
conjunction with holds-inst for comparison of time points. 
For example, if we define 
(Uexi ?r.eli 9reJ2) s 

(i) There exists time point ?tl at which 9rell is true 

(ii) There exists time point ?t2 at which ?rel2 is true 

(iii) ?t2 = ?ti +1 

then the rule for Hext is given by ; 

(H9xt ?rell ?rel2} <- (holds-inst ?rell ?tl) ' 

(holds-inst ?rel2 ?t2) 

<eq 7t2 (-*■ 7ti 11) 

By the development of such a temporal logic, we allow 


a powerful query language for the history. It allows us to 
reason over time instants as well as temporal intervals. 



CBAPTER 4 


IMPLEMENTATION OF A TEMPORAL LOGIC PROGRAMMING SYSTEM 

4 . 1 Introduction 

In this chapter we present an overview of the 
implementation of a temporal logic programming system. In 
this design we capture the formalism presented in the 
earlier chapter. 

4.2 Notion of Temporal Stacks 

Handling of state , time and history in the context ,of 
planning is achieved by suitably modifying the non-temporal 
logic programming shell. Along with the usual stacks 
required for the inference process (in an iterative 
fashion), the shell must now maintain what are called 
"temporal stacks" to keep track of the database changing 
with time. It is these stacks which store the time i^ap of 
the plan as it is executed. 

The predicates in the user’s plan generating program 
can be of two types - teuporal and non-temporal. The 
truth values of the temporal predicates change with time. 
The non-temporal predicates are unaffected by the state of 
the Blocks World and their truth values remain constant with 



40 - 


■time. Thus posn may toe regarded as a temporal predicate. 
CposTi A ?x ?y 9z) will be satisfied toy different values of 
9x , ‘?y , ?z as the position of block A changes with 

time. In contrast, color is independent of time in our 
Blocks World as there are no actions that cause a change in 
color. (color A blue! continues to toe true in any state 
of the Blocks World. The truth values of the different 
temporal predicates describe the state of the world at any 
given time. So stacks have to be maintained for these 
predicates to reflect truly the notions of changing states, 
history and time. The top of the stack stores the "current** 
state of the planning world. We go down the stack to 
retrieve information about earlier instants and query about 
history . 

4.3 Types of Temporal Stacks 

By the nature of the arguments that the temporal 
predication involves, the stack required to be maintained 

I* 

for the temporal predicate varies accordingly. There are 
four distinct types of temporal stacks necessary ( type-l ■, 
type-2 , type-Z , type-4 ) for the different classes of 
predicates. This classification helps in storing and 
retrieval of information about predicates. 

(1) type-1 stack This type of stack is maintained 
for temporal, predicates which have no arguments at all. 
For example, is-grippsd is a temporal predicate which 
has no arguments. It is either True or False at 



41 


different instants of time. 

(2) type-2 stack This type of stack fs maintained 

for temporal predicates which have all their arguments 
as keys, is-on is a predicate of this kind. It defines 
a relationship between two entities (blocks ). Both its 
arguments constitute the key and must be specified to 
uniquely define the relationship. For a given key it is 
either True or ‘ False with time. 

(3) type-3 stack This type of stack is maintained 

for predicates where none of the arguments are keys. 
posn-hand is an example of such predicate. The 
different coordinates of the robot ar» are mentioned 
as attributes of the implicit entity - the robot arm. 

Here, the attributes of a null key are recorded with 
time. 

(4) type-4 stack This type of stack is maintained 

for predicates where some of the arguments are keys. In 
the predicate xs-posn we assert positional coordinates 
(attributes) about a key item - the block. The 
attributes of a key are reco-rded for’ keeping track of 
state, history and time. 

4.4 Creation of Temporal Stacks 

The temporal stacks are created at the beginning 
of execution of the logic program for plan generation. 
The list of predicates (relations) for which stacks are 



42 


to be maintained are decided upon examination of the 
plan generation rules supplied by the user. It is only 
for the independent state observation predicates that 
temporal stacks are maintained. Inference of thte 
dependent state observations can be done from 
of the independent ones. 

The type of the stacks to be maini i 
deducible from the initial declarations of 
Therefore, on knowing the relations for which st 
to be maintained and the type of the stacl 
maintained the creation of stacks at run-time 
well-defined. Further, these stacks can be initi 
with the given facts in the initial configuration < 
Blocks World. 

For example, from the rules specified for 
Blocks World, we decide to maintain stacks for is-# 

, is-posn-hand , gripped , The initialisation of 
stacks with the given data is as shown below. 

The initial description of the Blocks-World is given \ 

(defasrt 1 (block A)) 

(defasrt 2 (block El) 

(defasrt 3 (block C) ) 

(defasrt 4 (block Dl) 

(defasrt 5 (block Ell 
(defasrt 6 (block F)) 



43 


Cde-fasrt 7 (is-posn All 3}> 

(defasrt S (is-posn B 1 1 D) 

(defasrt 9 (is-posn C 2 2 5)) 

(defasrt 10 (is—posn V 2 2 2)) 

<' defasrt 11 (is—posn E 3 3 3}) 

(defasrt 12 (is—posn F 4 4 2) ) 

(defasrt 13 (is-posn-hand 0 0 0} > 

The initialised stacks are as shown below : 

(posn ((A) (0 T 1 1 3)} 

((B) (0 T 1 1 1}} 

((C) (0 T 2 2 5)) 

((D) (0 T 2 2 2)) 

(<E) (0 T 3 3 3)) 

<(F) (0 T 4 4 4))} 

(posn -hand (() (07000})) 

(gripped <(} (0 F)}) 

4.5 Update of Temporal Stacks 

Regarding the update of the temporal stacks, we 
have to settle two major issues - (1) nben to update 
the temporal stacks ? and (2) Wo« to ui>date the 
temporal stacks ? 



44 


4.5.1 When to update the t^aporal stacks ? 

It may be worthwhile to recapitulate that the 
rules for a desired stats predicate are written in a 

particular manner. The first rule has a state 

* 

observatioTt predicate in the antecedent. If it fails to 
detect the desired state {by the failure of the state 
observation predicate) then it causes the desired state 
to be brought into existence by activating appropriate 
action rule for it. The state observation predicates 
can be .„.iBdSRe,aden t , or dependent . Intuitively it is 
clear that to reflect the changes in state with time of 
the world, which is being modelled, updates of the 
temporal stacks must take place when 

(1) time-setter is inferred implying that a 
primitive action has been performed. 

i 

(2) desired state predicate with an independent ' 
state observation predicate is inferred by using an 
action rule for it. 

The justification of the previous statement is as 
follows. (1) When a pr imitive action or a time— setter 
is inferred, a state transition takes place and some of 
the existing predications will cease to become true 
and/or new predications may become true in the new 
state. This is because the time-setter was invoked 
only when the desired state predicate, of which it is 
the antecedent, could not be inferred by observation 



- 45 - 

I 

I- 

\ 

alone. (2) When a desired state predicate is inferred 
by an action rule for it, a subtask for achieving the 
overall task , in the context of planning is 
accomplished. This accomplishment may have involved 
achieving other subsidiary desired states and invocation 
of ti»e-setters in the process. The overall 

accomplishment has to be reflected in the truth value of 
the state obseri^ation predicate used by the desired 
state predicate as the observation predicate is 
independent. Let the state of the planning world before 
the inferring of the desired state predicate be 
and the state after the inferring be S^. The independent 
state observation predicate was not true in but 

becomes true in S^. Therefore, the temporal stack for it 
must be accordingly updated when the desired state 
predicate is inferred with the current time stamp. In 
this context, it may be worthwhile to mention that no 
update of the temporal stacks takes place when a 
desired state predicate with dependent state 

observation predicate is inferred. This is because the 
state observation predicate of the desired state 
predicate is in turn dependent on other independent 
state obseri/ation predicates, the stacks corresponding 
to which were properly updatjed when other time-setters 

5 ^ 

were inferred in proving the first desired state 
predicate. 


4.5.2 How to update the temporal stacks 1 



46 


The specification of the types of .the tesaporal 
stacks provides significant clues regarding the 
procedures for updating the temporal stacks. In general, 
a temporal stack has assertions about attributes of 
key-items at different instants of time as its 
individual entries. The generalised representation of 
any temporal stack is as follows 

( ((key^) (timej^ T/F attr^^ attrg ... attr^) 

(timeg T/F attr^^ ' ‘ ‘ ' ‘ ' 

(time^ T/F attr^^ attrg ... attr^)) 


((key^) 

(time 

«Vk 

T/F 

attr^^ 

attrg 

. . . attr^) 


(time^. 

T/F 

attrj^ 

attrg 

... attr^ ) .... 


(time„ 

z 

T/F 

attrj^ 

attrg 

. . , attrj^) ) ) 

where 

(1) key^^ 

, keyg 

f • * 

. key^ 

, i = 

1,2,.,. represent 


collection of entities needed for viniquely 
identifying the temporal relation. It may be nil in 
case of type-3 stacks. 

(2) timcj^ , timeg , ... time^ , 1= 1,2,... represent 
different instants of time when the attributes of 
the key- items were asserted or retracted. 



47 


(3) T/F is a flag (either T or F) for denoting 
whether the relation involving the key-items and the 
attributes is True or False at the specified instant 
of time . 

( 4 ) att r > attr ^ j • * • attr ^ ^ denote 

the different attributes which are asserted or 
retracted about the key- items at the specified 
instants of time. When the stack is of type-2 
there are no attributes in a stack entry. The key 
comprises of all the arguments . 

The update of the temporal stacks involves two 
principal actions - assertion and retraction. The 
actions are comparable to the specification of “addlist" 
and "deletelist" in other planners such as STRIPS 
[4,10]. An "addlist" is a list of facts that become true 
when an event becomes true ; a "deletelist" is a list of 
facts which cease to be true when the event occurs. 
Similarly in assertion we claim to make a certain 
relation involving key-items and its attributes true at 
a certain point of time. Retraction is just the opposite 
of assertion. Here, we claim that a certain relation 
involving key- items and its attributes ceases to be true 
when an event occurs. For the purpose of assertion and 
retraction, a special predicate esserth is provided in 
the temporal logic programming system. This can be used 
for storing and removing temporal facts with appropriate 



48 


time stamps. For example, 

(asserth (is—posn A 1 23)) 

asserts the position of the block A to be (123) at 
the current instant of time in the position stack. 
Retraction of a relation can be achieved by asserting 
the negation of the relation. For example, 

(asserth (not (is-clear A))) 

retracts the fact that a is clear from from the 
database i.e. A ceases to be clear from the current 
time instant . 

The set of rules, supplied by the user, is pre- 
processed and the temporal assertions to be made are 
included in the form of (asserth <relation>) , where 
<relation> is any predication (or negation of 

predicate) of the observation kind, as antecedents of 
different desired state predicates. These predicates 
have time-setters as antecedents in the last rule for 
them. For example, the desired state predicate posn— 
hand has a set of rules given by 

(1) (posn-hand ?x ?y ?z) <- 
( is-posn-hand 7x 7y 7z) 

(2) (posn—hand 7x ?y 7z) <— 

(block 7block) 

(is-grasp ?bXock) 

((asserth (is—posn ?block 7x 7y 7z>) 



a&ii} 


(3) {posn-hand ?x ?y ?z> <- 
( assert h (is-posn-hand ?x ?y 7z)} 

(^} 


(fail) 


(4) (posft-hand ?x ?y ?z) <- 
(move-robot-arm ?x ?y ?z) 


Here, t.he first rule for positioning the robot 
arm to a set of arbitrary coordinates checks whether 
the hand is in that position or not. If not, then the 
second rule fires. In this rule we first check for the 
pre-condition (is-grasp 9block} i.e. whether a block 
is grasped by the robot arm at the current instant. If 
it is, then the new position of the block is asserted to, 
be the new position of the robot arm at the next time 
instant obtained by physically moving the robot arm . 

The special predicate (^) has no arguments. As a 
goal this succeeds immediately. However, it has side- 
effects which alter the way backtracking works 
afterwards. The effect is to make inaccessible the 
place-markers for certain goals so that they cannot be 
satisfied. Hence, if appears in seme rule and is 



satisfied, then the program becomes committed to all j 
choices ma<ie after the parent goal was invoked - 
Therefore, when the second rule fails due to the last 
antecedent - <fail} , ((§>) prevents attempts to 

resatisfy ( is~grasp ?block} or (assertb <is-pt>sn 
?block ?x ?y ?z)} - It instead tries the third rule 
and so on till it is finally satisfied by the last rule. 
The effect of assert h is to place all its arguments 
(instantiated relations) temporarily into a list. Only 
when the desired state predicate gets satisfied by the 
rule with the time-setter in the antecedent, is the 
time incremented and the updates made permanent on the 
temporal stacks with the new time stamp. 

Let us introduce two new terms - ei ament ary 

desired state predicates and compound desired state. 
predicates. The elementary desired state predicates 

are' those which do not invoke any other desired state 
predicate, in order to be inferred. They cause a time- 
setter to be invoked when the observation rule fails. 
The compound desired state predicates are those which 
may invoke other desired state predicates in order to 
be inferred by their action rules. In the foinnulation of 
the Blocks World, predicates such as posn , grasp , 
clear # on etc- are examples 'of compound desired state 
predicates. They invoke posn-hand , grip , ungrip in 
order to be inferred by their action rules. Predicates 
such as f ip * posn— hand are examples of 



■. u' '• I iv ■' u ui \ I 

1 i. T.. KANPUR 


....yyo.AX0.4A40. 

flemmntary desired state predicates as they first 
observe and then invoke time— setters such as close— 
grijpper , open— gripper ^ move— robot-arm in order to be 
inferred. 

The BJethod of pre-processing the plan-generation 
rules in order to generate the appropriate asserth' s 
in the antecedents of the rules for the various desired 
state predicates is as follows ■■ 

(1) For all elementary desired state predicates 
(edsp) with independent state observation predicates 
( sopi ) , introduce the rule 

(edsp) <- (asserth (sopi}> 

(€*} 

(fail) 

In the Blocks World, grip is an elementary desired 
state predicate with the independent state observation 
predicate - is-gripped . So after pre-processing, 
the rules for grip become 
{grip! <- (is-grippedl 

(grip} <- (asserth (is-gripped)} 

\ 

(fail) 

(grip) ttJose-gripper} 



(2) For all compoun<i desired state predicates (cdsp) 
with independent state observation predicates (sopi), 
examine the antecedents in the action rule for the 
coepound desired state predicate. Assert the 
independent state observation predicate as an 

antecedent of the last eleeentary desired state 
predicate invoked in inferring the compound desired 
state predicate by the action rule. Include the state 
obser vat ion predicates of the other desired state 
predicates invoked before invoking the last eieaentary 
desired state predicate as pre-conditionss of the 
assert. For example, posn is a compound desired state 
predicate with an independent statte observation 
predicate is-posn . The action rule for posn is 
given by 

(posn ?bIock ?x 9y ?z> (block ?block) 

(grasp ?block> 

(posn-hand ?x ?y ?z} 

Here, posn-hand is the last elementary desired state 
predicate invoked in inferring posn by the action 
rule. Therefore the rules for posn-hand after pre- 
processing become as mentioned earlier in the section. 
The pre-processing of plan-generation rules helps in 
associating all update actions of temporal stacks with 
the inferring of time-setters . 


4.8 leisettiog Time 



Time has to be reset and effects of temporal 
actions undone when the logic programming system enters 
the bstcktretcking mode. In this context, handling of 
the temporal stacks while the logic programming system 
backtracks becomes important. Each Htte-setter when 
inferred is pushed into the predicate stack with a 
special flag. The time stamp generated after inferring 
the time-setter is 'also noted. As stated earlier, the 
rules for plan generation are pre-processed so that the 
temporal actions of desired state predicates , which 
are not time-setters are reflected as the update 
action of the terminal time-setter which will be 
invoked when trying to satisfy the desired state 
predicate. Therefore, while backtracking and undoing 
temporal assertions, it suffices to consider time- 
setters only. When a time-setter is popped out of the 
predicate stack, the various entries in the different 
temporal stacks with the time stamp of the time- 
setter are retracted . The clock is also decremented by 
one unit. This sets the state of the world to the one 
which existed before the backtracked » ti*e— setter was 

inferred. 

For example, let the position of block A be (1 2 
3) at the 7th instant of time. Owing to <»oi/e-roi>ot-ar» 
4 5 6) at the 10th instant the position of A changes 
and i« asserted to be (4 5 5) . Iltasrefore the position 
stack at the li^h instant ,^ia, 



(posn ((A) (» 7 <7 T 1 2 3} C10 7 4 5 6>> . . .> 

Now, in the backtracking mode, when (wove-robot-arn 4 5 
6J with the time-stamp of 10 is retracted, the 
assertion actions at the 10th instant are undone and the 
position stack becomes : 


(posn <(A} (9 7 


.) . 


(7712 3}} 


} 



CHAPTER 5 


AHALYSIS AND E7ALDATI01I OF THE SYST^ 


6 . 1 Special Features Of The System 

The temporal logic programming system is different 
from some of the existing systems in certain ways. The 
existing plan generation and robot problem-solving systems 
such as STRIPS operate as a forward deduction system. 
Forward rules (F - rules) are fired in the course of 
generation of the plan and change one state description into 
another. In this way , the sequence of actions needed for 
achieving the goal state is obtained. For modelling the 
changes in the state of the world being modelled, each 
forward rule must specify three components - precondition 
formula, delete list and add list. We have already 
encountered the last two terms. The precondition formula is 
a predicate calculus expression that must logically follow 
from the facts in a state description in order for the I- 
rule to be applicable to that state description. 

The temporal logic programming system and the method 
outlined for prescribing rules for plan generation enable 
similar problem solving in a backward chained fashion. This 
allows construction of robot plans in an efficient fashion 
as we work backward from k goal expression to an initial 



state description , rather than vice versa. The strategy 
employed for this purpose is to apply a conjunction of 
antecedents consisting of preconditions and assertions in 
the rules of the desired state predicates. This has been 
illustrated before. Along with its functioning as a backward 
chained system, the designed system performs the role of a 
Time Hmp rtanager <TMH} [2]. It is able to store, update 
and retrieve from a long-term store of time tokens. The 
temporal understanding capability of the system is a 
consequence of its ability to handle time. It keeps track of 
the history of the world as a plan executes and is 
subsequently able to answer about validity of different 
relations at different instants of time in the course of 
execution of the plan. 

5.2 Declarations required in Temporal Logic Programming 

(1) ( Time-setters pactj^ pactg pact^) 

(2) ( Staie-preds (dspj^ (kj^ ... 

(dspg sopg ng (k^ 


(dspj^ sop^ n^ (kj^ ... > 

where pact^ denotes ith primitive action 

. dspj^ denotes ith desired state predicate 
sopj^ denotes ith state observation predicate 



57 


denotes no. of arguments in ith desired state 

predicate 

(kj^ ... denotes the position of the key- items in 

the list of arguments of the desired state predicate. 

These declarations are to be made by the user along with the 
set of rules for plan generation. 

For example, in the formulation of the Blocks World, 
the declarations to be made by the user are : 

(Tsme-^smiter s open-gripper ciose-gr ipper move-robot-arm > 

(Staie-preds fpiace is-place 4 (D) 

<posn is-posn 4 <1>) 

(grasp is-grasp 1 <1}> 

^clear is-clear 1 (!)> 

(on is-on 2 (1 2)> 

(hmndempty is-haridempty OJ 
(posn-hand is-posn-hand 3' ()} 

(grip is— gripped 0 (■>> 

(ungrip is-not-gripped 0 0) 

) 


5.3 Bepresenting rules in Temporal Logic Programming = 

In general, the set of rules that will be used for 
plan generation and can be partitioned into three classes - 
(1) rules apecifjring the inferring of desired state 
predicates (2) rules specifying relationship between state 



otstr^^iioi, predicates . and (3) rules specifying inferring 
of met ion predicates. 

Writing rules of class (1) is fairly straightforward. 
The first rule observes whether the desired state exists by 
invoking the corresponding state observation predicate. 
The subse<iuent rules specify the antecedent states needed to 
be achieved for inferring the overall desired state. Here, 
the user is expected to clearly write any temporal 
assertions which are indirect and do not follow directly 
front the given rules nor declarations about desired state 
and sfat* observation predicates. To illustrate the point, 
we consider the rules for the desired state predicate 
ungrip . The rules are as follows 

(1) (ungripJ <- (is-not^gripped) 

(2) (ungripJ' (msserth (not (is-gripped) }) 

ffaii; 

(3) (ungrip) <- (open-gripper) 

The desired state predicate ungrip uses a state 
observation predicate which is not independent. The rule to 
infer it is given by 

(is-not‘“'gr ipped) ■ (not-' (i-b'^'ripped)) 

Initially if the robot are is gripped, then on achieving 
the desired state ungrip we need to assert that it is no 



is-not—gr ipped 


longer gripped. So we need to assert about 
after inferring ungrip. This, in effect, implies that the 
independent state observation predicate is—gripped must, 
be retracted after the inferring of ungrip . The- 

antecedent (asserth (not (is-gr ipped) ) } achieves this. The 
second rule of ungrip needs to be explicitly specified by' 
the user of the system. 

Defining the relationships between the state 

observation predicates and defining rules for action 
predicates are illustrated below. 

Some of the 'rules specifying relationships between 
state observation predicates are ; 

fis-piac# 9bIock ?x ?y ?x> <- (is-posn ?block ?x 7y ?z) 

(not (is-gr asp ?block)} 

f" 

( is—grasp ?bJock} <- (is-posn ?bIock ?x ?y ?z} 

(is-posn—hand ?x ?y ?z) 

< is-gr ipped > 

The action rules are typically computational in nature 
which return true. 

5.4 Scope for further improvement 

In the course of developing an Intel igent Logic 
Programming ,frasfiieworlE which would efficiently handle time, 
different problems had to be solved. Some of these . offered 
direct solutions while some required more complicated 



60 - 


methodfi for solving. 

Ono such problssi which did not offer a direct solution 
was in connection with update of temporal stacks. As stated 
earXiert the temporal stacks are to be updated when a 
t iu9~~s0tt0r is inferred. When the desired state predicate 
of which the time-setter is the antecedent has an 
independent state observation predicate (with a temporal 
stack reserved for it), the update action is fairly 
staraightforward. After the inferring of the tine-setter 
the state observation predicate has to be asserted to be 
true. However, when the desired state predicate in 
question uses a dependent state observation predicate, the 
update actions are not so obvious. Consider the following 
example of a restricted version of the Blocks World domain 

where the only desired state predicate is on - The plan 

* 

generation rules and the user declarations are as follows 

(on ?blocki ?block2} <- <is-on ?blocki ?block2) 

(on Pblockl ?block2} <- (do-stack ?blocki ?block2} 

(is-on ?bIockS 9block2f <• (is-posn ?blockl ?xi ?yl ?zl> 

(is-posn ?block2 ?xi ?yl ?z-comip) 
(height fblocki ?hl} 

(height ?bIock2 ?h2) 

?z-comp (add ?zl 

(product 0.5 
(product 0.5 



61 




<> ?zl ») 
(> ?z2 0) 


itimm’-s0tter$ dlo-Mimck) 

(stit^-pfds (on is-on 2 (1 2)) 
<() is-posi) 4 <!}} 


dina* th» st«t« observation predicate is-on is dependent 
on the independent observation is~posn , we do not 

maintain a separate srack for it. It is only the is-posn 

for which a temporal stack is maintained. Now, assume the 
initial declarations are as follows : 

(block Ai 
(block S) 

(hoight A 2) 

♦ 

(height B 21 ‘ 

(is-postt A S S 
(is’-posn 8 2 2 2) 

The desired state (of* A 81 has to be aphieved by the 
action rule for o» - So, the time-setter — do-stack 
has to be inferred. In oreder to satisfy the observation 
(is—ph A 8^ at this point of time ,{in the new state of the 



62 


Blocks World), the positional coordinates of A have to be 
changed. That is, after achieving the desired state (is- 
posn A 2 2 4) has to be asserted with the current time- 
stamp (1) in the position stack. (is-posn B 2 2 2) has to 
remain unaffected. 

To impart intelligence to the system, so that it is 
capable of doing such deductions would involve a procedure 
of trial and error. We would have to satisfy a dependent 
state observation predicate by satisfying the independent 
observations on which it is dependent. This involves 
rearranging and asserting about the independent state 
observation predicates which appear as antecedents of 
different rules. 

The correctness of such a proof method could not be 
clearly outlinad. Hence, at this stage the system would 
expect an explicit declaration from the user of the form ; 

(on ?blockt 9biock2) <- (is^-on ?biockl ?bJock2} 

(on 2b lock! ?bleck2) <'- f is-posn ?block2 ?x ?y 

(height 7blockl 7hl) 

(height 7block2 7h2i 
(9 Px-comp (edd, 7z 

(product 7hl} 

. (product 9.5 

?h2}n 

"" ' (ptsserth (is^posn ?biockl ■■?x / 7 y 



63 


ffsilJ 


(on ?bIocki ?t>lock2) <— ('ti'me—set'te'r ) 


5.5 Conolusion 

The major achievement of the Temporal Logic 
Programming fojrmalism presented in this thesis is that it 
allows Planning and temporal Understanding to take place in 
a logic programming framework. It is becoming possible to 
handle temporal notions in the logic programming 
environment . 

Further, the formalism circumvents the problem of 
enumeration of frame axioms. The necessity of maintaining 
explicit state variables as additional arguments pf 
predicates in the rules of the logic program and stating the 
effects and non-effects of actions is obviated in this 
approach. The formalism permits a strong basis for reasoning 
with time. The query mechanism for deduction of temporal 
relationships is powerful. The hemdling of time, state and 
history in this formalism adds a new dimension to planning 
techniques. It is now possible to generate planning actions 
with reference to past situations. To illustrate in terms of 
our familiar Blocks World, it is possible to plan "Place 
block 4 where block B was when block C was on top of block 
D“ using the temporal logic programming formalism. 



REFERENCES 


(1) Allen, J.F 1984 •• Towards a General Theory of Action 
Time, Artificial Intelligence, 23 pp 123-154 

(2) Charniak.E and McDermott, D 1985 ; Introduction 

Artificial Intel ligence,Addison-Wesley Publishing Compan 

(3) Clocksin.W.F and Hellish, C.S 1986 : Programming 

\ 

Prolog, Springer-Verlag, Berlin 

(4) Fikes.R.E and Nilsson, N.J 1971 : STRIPS - a new appr 
to the application of theorem proving to problem solv 
Artificial Intelligence, 2 (314) pp 189-208 

(5) Green, C 1969 : Theorem proving by resolution as b 
for question answering systems. In MI4, pp 183-205 

(6) Kowalski, R 1974 : Logic for Problem Solving, Memo no 
Dept, of Computational logic, Oniv. of Edinburgh 

(7) Kowalski, R 1979 : Logic for Problem Solving, New Yor 

i 

North Holland 

(8) Mos 2 kowski,B 1986 : Executing temporal logic progi 

s 

Cambridge University Press 

(9) Nakamura, K if 86 ' Control of Logic Program Execu. 
based on functional Relation, 3rd International Conferenc 
on Logic Programming. 


APPENDIX- 1 


(comment, "the following are the set of plan generation rules 
to be used for the Blocks -World model " ) 


(consnent ''**************t^^******iii^**.*i*i^7^*.)t:^*i^>^" ) 
(comment " rules for desired state predicates ") 
( comment " *#***»**>|c3)(***!*:****sc****>t:**^****!t:**** ) 

(defasrt pll (place ?block ?x ?y ?z) <- 
(is-place ?block ?x ?y ? 2 ) 

) 

(defasrt pl2 (place ?block ?x ?y ?z) <- 
(block ?block) 

(posn ?block ?x ?y ?z) 

(ungrip) 

) 


(defasrt pol (posn ?block ?x ?y ? 2 ) <- 
(is-posn ?block ?x ?y ?z) 

) 

(defasrt po2 (posn ?block ?x ?y ?z) <- 
(block ?block) 

(grasp ?block) 

(posn-hand ?x ?y ?z) 

) 


(defasrt grl (grasp ?block) <- 
(is-grasp ?block) 

) 

(defasrt gr2 (grasp ?block) <- 
(block ?block) 

(clear ?block) 

(handempty) 

(is-posn ?block ?x ?y ?z) 
(posn-hand ?x ?y ?z) 
(grip) 

) 


(defasrt cll (clear ?block) <- 
(Is-clear ?block) 

(defasrt ol2 (clear ?block) <- 
(block ?blockl) 

(block ?block) 

(is-on ?bl6ckl ?block) 
(grasp ?blockl) 
(handempty) 

) 



(clefasirt onl 
) 


(on ?blockl ?block) <- 
(is-on ?blockl ?block) 


(defasrt on2 (on ?blockl ?block) <- 
(block ?blockl) 

(block ?block) 

(clear ?block) 

(clear ?blockl) 

(is-posn ?block ?x ?y ?z) 

(ht ?block ?h) 

(ht ?blockl ?hl) 

(= ?a-coinp (calc-ht ?a ?h ?hl)) 
(place ?blockl ?x ?y ?z-comp) 

) 


(defasrt hel (handempty) <- 
( is-handempty ) 

) 

(defasrt he2 (handempty) <- 

(= ?empx (find-empty-posn-x) ) 
(= ?empy (f ind-eapty-posn-y) ) 
(= ?empz (f ind-empty-posn-z) ) 
(posn-hand ?empx ?empy ?empz) 
(ungrlp) 

> 


(defasrt phi 
) 

(defasrt ph2 
) 


(posn-hand ?x ?y ?z) <- 
{ is-posn-hand ?x ?y ?z) 

(pofim-hand ?x ?y ?z) <- 
(move -robot -arm ?x ?y ?z) 


(defasrt grl (grip) <- 
* (is~f ripped) 

) 

(defasrt gr2 (grip) <- 

(close- gripper) 


) 


I 


(defasrt ugl (ungrip) <- 

( is-not-gripped) 

) ' 

(defasrt ug2 (ungrip) <- 

(asserth (not (is-gripped) ) ) 

m 

(fail) 

(defasrt ug3 (ungrip) <- 

(,op0H.^gripper) ■ , 


) 



( coMiaent 
( comment 
{ comment 

(def asrt 
) 

(def asrt 

) 

(def asrt 
) 

(def asrt 

) 

(def asrt 

) 

(def asrt 
) 

(def asrt 
) 


rules expressing relations among state observation predicates ‘ 
’‘***5»:***»cJ»:*!*:*****!|c*!jc**sk*****3»:*:**:tc**;^e*sic*******>t:*************>|t****' 

ipl (is-place ?block ?x ?y ?z) <- 
(is-posn ?block ?x ?y ?2) 

(not (is -grasp ?block)) 


igr (is-grasp ?block) <- 

(is-posn ?block ?x ?y ?z) 
<is-posn-hand ?x 7y ?2) 
(is-gripped) 


id (is-clear ?block) <- 
(block ?block) 

(not (is-loaded ?block)) 


isl (is-loaded ?block) <- 
(block ?blockl) 

(block ?block) 

(is-on ?blocki ?block) 


ion (is-on Tblockl ?block) <- 
(block Tblookl) 

(block tblook) 

(not (eq ?blookl ?block)) 
^8-poan ?block ?x ?y ?z) 

(ht ?block ?h) 

(ht ?blockl ?hl) 

(= ?z-coiBp (calc-ht ?2 ?h ?hl)) 
(is-posn ?blockl ?x ?y ?2-comp) 


ihe (is-handempty) <- 
(not (is-gripped)) 


ing (is-not-gripped) <- 
(not (is-gripped)) 



61 - 


{COBSaent "!**J*:i*:)+:j*!!*!*)|(**>K*****:******!*c*i*c**!t:)»c!*:***!tc**" ) 
.(comment "rules defining temporal relationships") 
(comment “^****>t:**>|:*;*c*:<c****:****>)t***>|t***5tc*******” ) 


(defasrt dur (during ?tl ?t2) <- 
(not (null ?tl)) 

(not (null ?t2)) 

(> (car ?tl) (car ?t2)) 

(< (cadr ?tl) (cadr ?t2)) 

) 

(defasrt str (starts ?tl ?t2) <- 
(not (null ?tl)) 

(not (null ?t2)) 

(eq (car ?tl) (car ?t2)) 

(< (cadr ?tl) (cadr ?t2)) 

) 

(defasrt fin (finishes ?tl ?t2) <- 
(not (null ?tl)) 

(not (null ?t2)) 

(eq (cadr ?tl)(cadr ?t2)) 

(> (car ?tl) (car ?t2)) 

) 

(defasrt bef (before ?tl ?t2) <- 
(not (null ?tl)) 

(not (null ?t2)) 

(< (cadr ?tl) (car ?t2)) 

) 

(defasrt ovr (overlaps ?tl ?t2) <- 
(not (null ?tl)) 

(not (null ?t2)) 

(< (car ?tl) (car ?t2)) 

(> (cadr ?t2) (cadr ?tl)) 

(> (cadr ?tl) (car ?t2)) 

) 

(defasrt met (meets ?tl ?t2) <- 
(not (null ?tl)) 

(not (null ?t2)) 

(eq (addl (cadr ?tl)) (car ?t2)) 

) 

(defasrt eql (equal ?tl ?t2)<- 
( not (null ?tl)) 

(not (null ?t2)> 

(eq (car ?tl> (car ?t2)) 

(eq (cadr ?tl) (cadr ?t2)) 

) . ' ^ 



( comment " **;*****!♦:!♦:***********•• ) 

(comment " user declarationss ”) 

( comment " ******5*:*5*:!»c*He>»:*3*:s»c5*:**i1c " ) 

(time* setters open“gripper close~gripper move -robot “arm) 

(state-preds (place is-place 4 (1)) 

(posn is-posn 4 (1)) 

(grasp is-grasp 1 (1)) 

(clear is-ciear 1 (1)) 

(on is-on 2 (1 2)) 

(handempty is-handempty 0 ( ) ) 

(posn-hand is-posn-hand 3 ( ) ) 

(grip is-gripped 0 ()) 

(ungrip is-not-gripped 0 ()) 

) 

(comment "****sk***5>:>t:***3|c**>|c**;*i»:*****:<c******" ) 

(comment "various computational definitions") 

( comment " *******5+:****!jt********>l:>lc***:<ci(c*3*:)*:** " ) 


(defcomp close-gripper dum) 

(defcomp move- robot- arm duml) 

(defcomp open-gripper dum) 

(de dum () t) 

(de duml (a b c) t) 

(de oalc-ht (a b c) 

(cond [(and (numberp a) ( number? b) (number? c)) 

(fix (add a (product .6 b) (product .5c)))] 

[t (list *a_d_d a (list *p_r_o_d .5 b) (list ’p_r_o_d .6 c))] 

(setq $countx 47) 

(setq $county 47) 

(setq $countz 47) 

(de f ind-empty-posn-x () 

(setq $countx (addl $countx)) 

(readlist (append (list ’e ’m ’p *- ’X) (list (ascii $countx)))) 

) 

(de f ind-empty-posn-y () 

(setq Scounty (addl $county)) 

(readlist (append (list ’e ’m ’p ’Y) (list (ascii $county)))) 

) ' ■ 

(de f ind-empty-posn-z () 

. (setq Scountz (addl $countz)) 

(readlist (append (list ’e ’m 'p ’- 'Z) (list (ascii $countz)))> 

) . ' \ 

(defcomp eq eq) v''''''"" 

(defcomp > >) 

(defcomp < <) • ' ; 

(defcomp and and) 

(defcomp null null) 

(defcomp eq eq) 

(defcomp equal equal,) 

( comment " ^****)tc*****!<c*)»:***)tc*********4:****:tc***$3|J*************)tc****)|c*** 



APPENDIX-2 


(comiaen't ■■*******************5*:*!<c*******:**)*:****i<c******;******:K**>K*5*:*****>*:*'‘ ) 

(comment "The following are the set of assertions which describe an 
initial state of the Blocks-World (refer APPENDIX - 3). 

There are six blocks - A,B,C,D,E,F and their heights and 
positions are as indicated by "Ht" and "is-posn" predicates. 

We find that A is on B, C is on D, E and F are clear. 

The hand is at the coordinates 0,0,0 as indicated by 
"is-posn-hand" . 

The clock is set at 0. " ) 

(comment "****>>‘*********>l<!(«*************:*3t:*:***i|c**5t:***5^:***i(c)(c5t!)jc****^****=ic>k*:” ) 

(defasrt 1 (block A)) 

(defasrt 2 (block B)) 

(defasrt 3 (block O) 

(defasrt 4 (block D)) 

(defasrt 5 (block E)) 

(defasrt 6 (block F)) 

(defasrt 7 (ht A 2)) 

(defasrt 8 (ht B 2)) 

(defasrt 9 (ht C 2)) 

(defasrt 10 (ht D 4)) 

(defasrt 11 (ht E 6)) 

(defasrt 12 (ht F 4)) 

(defasrt 13 (is-posn A 1 1 3)) 

(defasrt 14 (is-posn Bill)) 

(defasrt 16 (is'Posn C 2 2 5)) 

(defasrt 16 (is-posn D 2 2 2)) 

(defasrt 17 (is-posn E 3 3 3)) 

(defasrt 18 (is-posn F 4 4 2)) 

(defasrt 19 ( ia-posn-hand 000)) 


( comment " ************!tJ**5*:!**********************************’^************^ 



(comment "An interactive session with the 

Temporal Logic Programming system") 

{ comment " ) 

(comment "Blocks-Wor Id- rules is the file in APPENDIX - 1") 

(comment "Blocks-Wor Id-description is the file in APPENDIX - 2") 
(comment "'♦:**************!*:!tt»c^c!*:**xc;***:tt5|c*5)c***i*:***)»:****5|c*********»c>*:)*:*" ) 


[13(dskin Blocks-World- rules) 

[load Blocks-World-rules] 

( Blocks-World-rules ) 


C 2 3 ( dskin Blocks-World-description ) 

[load Blocks-World-description] 
(Blocks-World-description) 


(comment "We generate a plan in the following way") 

[33(plan (on C E)) 

The plan is as follows ... 

The CLOCK is -set to 4 
£03 (move-robot-arm 225) — >[1] 

£13 (close-gripper) — > £23 

£23 (move -robot -arm 337) --> [3] 

£33 (open-gripper) — > £4] 
nil 

(comment "The plan is in terms of time-setters 

which cause the clock to be incremented on being, inferred" ) 

(co 3 Dament "To do temporal analysis of the Blocks-World we use ,tbe 
function ‘query’ ") 


(comment "The following finds all the time points at which E is clear") 
£43 (query (holds-inst (clear 1) ?t) ) 
proved ! 

answer is :- *** 

•?t = 0 


*** more answers wanted ? (y/n) y 
•♦jk* answer is : - 
?t = 1 

*** more answers wanted ? (y/n) 7 
***: answer is 
■?t = 2 

more answers wanted 7 (y/n) y 
*** no more answers possible . 

ok. 

nil 



(comment "The following examines the time 
intervals in which E is clear") 

[5] (query (holds-int (clear E) ?t)) 

proved i 

*■*■* answer is : - 
?t = (0 2) 

more answers wanted ? (y/n) y 
*** no more answers possible . 


ok. 

nil 

(comment The following query finds the positions of 
the different blocks at <4th time instant" ) 

[63 (query (holds~inst (posn ?block ?x ?y ?z) 4)) 

proved ! 

*** answer is : - *** 

?block = A 
?x = I 
?y = 1 
?z = 3 

*** more answers wanted ? (y/n) y 
answer is : - 
?block = B 
?x = 1 
?y = 1 
7a = 1 

*** more answers wanted 7 (y/n) y 
answer is : - *** 

7block = C 
?x = 3 
?y = 3 
?a = 7 

*** more answers wanted 7 (y/n) y 

*** answer is : - 

?block = D 

7x = 2 

7y = 2 

?a = 2 

*** more answers wanted 7 (y/n) y 
answer is 
?blook = E 
?x = 3 
?y = 3 
7z = 3 

*** more answers wanted ^ (y/n> y 
*** answer is *** ■ ' ' ' ' 

?block = F 
?X = 4 
?y = 4 

?z = Z ■ 

*** more answers wanted 7 (!^/n) iy 
*** no more answers possible . 



(comment “the following query finds the different 
positions of all the blocks in different 
time intervals") 

[7] (query (holds-int (posn ?block ?x ?y, ?z) ?t)) 
proved ! 

*** answer is : - *** 

?block = A 
?x = 1 
?y = 1 
?z = 3 
?t = (04) 

*** more answers wanted ? (y/n) y 
answer is : - 
?block = B 
?x = 1 
?y = 1 

?B = 1 

?t = (0 4) 

*** more answers wanted ? (y/n) y 
*** answer is - *■** 

?block = C 
?x = 2 
?y = 2 
?s = 5 
?t = (02) 

*** more answers wanted ? (y/n) y 

*** answer is *** 

?block = D 
?x = 2 
?y = 2 
?a = 2 
?t = (0 4) 

*** more answers wanted ? (y/n) y 

*** answer is *** 

?block = E 
?x = 3 
?y = 3 
?z = 3 
?t = (0 4) 

*** more answers wanted ? (y/n) y 

sK** answer is 

?block = F 

?x = 4 

?y = 4 

?a = 2 

?t = (0 4) 

*** more answers wanted ? (y/n) y 
*** answer is : - *** 

?block = C 
?x = 3 
?y = 3 
?2 = 7 
?t =(34) 

*** more answers wanted 7 (y/n) y 
*** no more answers possible . 



(comment "The following query tests for the 
'equality’ of temporal intervals") 

[83 (query (holds-int (on A B) ?tl) 

(holds-int (clear F) ?t2) 

(equal ?tl ?t2)) 

proved * I 

*** answer is : - *■** 

?tl = (0 4) 

?t2 = (0 4) 

*** more answers wanted ? (y/n) y 
no more answers possible . 

ok, 

nil 


(coBHoent "The following query tests whether two 
time-intervals meet or not" ) 

[93 (query (holds-int (on CD) ?tl) 

(holds-int (on C E) ?t2) 

(meets ?tl ?t2)) 


proved ! 

*** answer is *** 

?tl = (0 2) 

?t2 = (3 4) 

*** more answers w^ted ? (y/n) y 
*** no more answers possible . 


ok. 

nil 


(coBBuent "The following query finds the time intervals in which 
the robot arm was gripping some block" ) 

[10] (query (holds-int (grip) ?tl)) 

proved I 

answer is ; - *** 

?tl = (2 3) 

more answers wanted ? (y/n) y 
no more answers possible . 


ok. 

nil 

(coMneht "Now, let us stop doing temporal analysis for a minute and do 
something more to the Blocks -World. 

Note when we plan again, we have the alternative of resetting 
the clock and starting all over from the initial state or 
continuing from the point where we' left" ) 



[11] (plan (on D B) (clear E) (grasp F)) 

*** Continue from previous state (y/n) ? y 
The plan is as follows . . . 

The CLOCK is set to 18 
[4] (move-robot-arm 1 1 3) — > [5] 

[§] (close-gripper) --> [6] 

[6] (move-robot-arm emp-X0 emp-Y0 emp-Z0) — > [7] 

[7] (open-gripper) — > [8] 

[8] (move-robot-arm 222) — > [9] 

[9] ( close- gripper ) — > [10] 

[10] (move-robot-arm 114) — > [11] 

[11] (open- gripper) --> [12] 

[12] (move-robot-arm 337) — > [13] 

[13] (close- gripper) — > [14] 

[14] (move-robot-arm emp-Xl emp-Yl emp-Zl) — > [15] 

[15] (open-gripper) — > [16] 

[16] (move-robot-arm 442) — > [17] 

[17] (close-gripper) — > [18] 
nil 

(comment "Now let us do temporal analysis") 

[12] (query (holds-int (clear E) ?t)) 
proved ! 

*** answer is : - *** 

?t = (0 2) 

more answers wanted ? (y/n) y 
*** answer is *• - 
?t = (15 18) 

more answers wanted 7 (y/n) 

*** no more answers possible . 


ok. 

nil 


(comment "The following query finds the positions of 
block A over all time-intervals") 

[13] (query (holds-int (posn A ?x ?y ?z) ?t) ) 

proved i 

answer is - ’t'** 

?x = 1 
?y = 1 

?s = 3 , 

?t = {06) 

*** more answers wanted ? (y/n) y 
answer is 5 - 
?x = emp-X0 
?y = eaip'^Y0 

c emp-Z0 . 

?t = (7 18) 

*** more answers wanted ? (y/n) y 
’ no more answers possible . 

•ok, 

nil 



(comment "The following query finds all the 
intervals in which any 
block was loaded") 

[14] (query (holds-int (is-loaded ?block) ?t)) 

proved 1 

answer is : - 
?block = B 
?t = (0 6) 

more answers wanted ? (y/n) y 
*** answer is ***■ 

?block = B 
?t = (11 18) 

*** more answers wanted ? (y/n) y 
*** answer is : - *** 

?block = D 
?t = (0 2) 

>♦;** more answers wanted ? (y/n) y 
w.**. answer is 
?block = E 
?t = (3 14) 

*** more answers wanted ? (y/n) y 
***■ no more answers possible , 


ok. 

nil 


(comment "By the following query we test whether one time 
interval is wholly contained in another") 

[15] (query (holds-int (on C E) ?tl) 

(holds-int (clear E) ?t2) 

(during ?tl ?t2)) 


proved ! 

*** answer is *** 

?tl = (3 14) 

?t2 = (0 18) 

more answers wanted ? (y/n) y 
*** no more answers possible . 

ok. 

nil 


(comment "The following query tests whether the 

intervals over which two relationships are 
true do overlap or not") 

[16] (query (holds-int (on A B) ?tl) 

(holds-int (clear D) ?t2) 

(overlaps ?tl ?t2)) 


proved I 

answer is '• - 
?tl = (0 6) 

?t2 = (3 18) 



[17] (query- (holds-int (posn C ?x ?7 ?z) ?t)) 
proved ! 

*** answer is *** 

?x = 2 
?y = 2 
?z = 5 
?t = {0 2) 

*** more answers wanted ? (y/n) y 
answer is *** 

?x = 3 
?y = 3 
?a = 7 
?t = {3 14) 

***■ more answers wanted ? (y/n) y 
answer is *• - *** 

?x = emp-Xl 
?y = emp-Yl 
?z = ei»p-Zl 
?t = (15 18) 

*** more answers wanted ? (y/n) y 
no more answers possible . 

ok, 

nil 

(comment "The following query finds the intervals in which D is clear 

[18] (query (holds-int (clear D) ?t)) 

proved 1 

answer is '• - 
?t = (3 18) 

more answers wanted ? (y/n) y 
no more answers possible . 

ok . 
nil 

(comment "The following query highlights 
an interesting facility. 

We can backtrack for the predicates 
‘holds-int’ and *holds-inst' in our temporal 
logic programming system. 

In this case it is the second unification for ?tl = (3 14) 
which answers the composite query" ) 

[19] (query (holds-int (posn C ?x ?y ? 2 ) ?tl) 

(holds-int (clear D) ?t2) 

(starts ?tl ?t2)) 


proved I 

answer is :*■ *** 

?x = 3 
?y = 3 

- 7 

’ ?tl = (3 14) 

?t2 = (3 18) 

*** more answeirs wanted ? (y/n) y 
*** no more answers possible . 



(comment "The following illustrates when a 
time-interval is said to 
occur before another") 


[203 (query (holds-int (on G E) ?tl) 
(holds-int (grasp F) ?t2) 
(before ?tl ?t2)) 


proved I 

*** answer is *** 

?ti = (3 14) 

?t2 = (18 18) 

*** more answers wanted ? (y/n) y 
*** no more answers possible . 

ok. 

nil 


(comment "The flexibility which the temporal system 

offers allows us to define new temporal relations 
as and when required. 

We illustrate this by defining 'always-true’ and ‘ sometimes-tru< 
below. 

' current- instant’ is a function which returns the current value 
of the clock") 

[213(defasrt alt (always-true Trelation) <- 

(holds-int ?relation ?t) 

(eq (car ?t) 0) 

(eq (cadr ?t) (current-instant) ) ) 

always-true 

C223(defasrt sot (sometimes-true ?relation) <- 

(holds-int ?relation ?t) 

(not (null ?t))) 

sometimes-true 

[23] (query (always-true (clear F))) . 

proved ! 

*■*■* more answers wanted ? (y/n) n 

ok. .. ;/■ 

nil 


(comment "The following query finds all the blocks . 

which have not been moved at all during the 
state transition of the Blocks-World ) 



— »a — 


[24] (query (always-true (posn ?block ?x ■?y ?z:))) 
proved \ 

*** answer is - *** 

?block = B 
?x = 1 
?y = 1 
?z = 1 

*** more answers wanted ? (y/n) y 
answer is : - *** 

?block = E 
?x = 3 
?y = 3 
?z = 3 • 

*** more answers wanted ? (y/n) y 
answer is : - 
?block = F 
?x = 4 
?y r 4 
?z = 2 

*** more answers wanted ? (y/n) y 
*** no more answers possible . 

ok. 

nil 


(comment “The following query finds all the blocks 

which were grasped at some point of time",) 

[26] (query (sometimes -true (grasp ?block))) 

proved \ 

*■**■ answer is *** 

?block = C 

*** more answers wanted ? (y/n) y 
*** answer is : - *** 

?block = C 

*** more answers wanted ? (y/n) y 
*** answer is ; - **■* 

?block = A 

*** more answers wanted ? (y/n) y 
*** answer is *** 

?block = D 

*** more answers wanted ? (y/n) y 
*** answer is 
?block s F 

more answers wanted ? (y/n) y 
*** no more answers possible . 


ok. 

nil